package cn.hesion.dataStructures.sortingorder;

import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.Arrays;

public class MergeSort {
    public static int count = 0;

    public static void main(String[] args) {
//        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] arr = new int[8000000];
        int[] temp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i]= (int) (Math.random()*8000000);
        }
//        System.out.println("排序前");
//        System.out.println(Arrays.toString(arr));
        Long before = LocalDateTime.now().toInstant(ZoneOffset.of("+8")).toEpochMilli();
        System.out.println("排序前系统时间毫秒数:"+before);
//        selectSortTD(arr);
        MergetSort(arr,0,arr.length-1,temp);
        Long after = LocalDateTime.now().toInstant(ZoneOffset.of("+8")).toEpochMilli();
        System.out.println("排序后系统时间毫秒数:"+after);
        System.out.println("本次归并排序共耗时:"+(after-before)+"ms");

//        MergetSort(arr, 0, arr.length - 1, temp);
//        System.out.println(Arrays.toString(arr));
        System.out.println("递归次数:"+count);
    }

    //分+合的方法 递归
    public static void MergetSort(int[] arr, int left, int right,
                                  int[] temp) {
        count();
        if (left < right) {

            //求中位数
            int mid = (left + right) >> 1;
            //对左边的进行递归分解
            MergetSort(arr, left, mid, temp);
            //对右边的进行递归分解
            MergetSort(arr, mid + 1, right, temp);
            //合并
            Merget(arr, left, mid, right, temp);
        }
    }

    public static void count() {
        count++;
    }
    //合并的方法

    /**
     * @param arr   需要排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right right 右边索引
     * @param temp  做中转的数组
     */

    public static void Merget(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        //开始循环两侧的数组
        while (i <= mid && j <= right) {
            //如果i所遍历到的数比j所遍历到的数小，则将i遍历到的数 存入temp数组中
            if (arr[i] <= arr[j]) {
                //存入temp数组
                temp[t] = arr[i];
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        //循环结束，可能一侧的数组中还有几个数残留，一般为较大数
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }

        //然后将temp的中的数再辅助进arr
        //重置t
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }

    }
}
